package org.gushi.datastruct.a06;

import org.gushi.datastruct.a06.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 平衡二叉树的实现
 * <p>
 * BinaryTreeInfo  : 属于二叉树打印工具的实现
 *
 * @param <E>
 */
public class BinarySearchTree1<E> implements BinaryTreeInfo {

    private int size;

    private Node<E> root;

    private Comparator<E> comparator;

    public BinarySearchTree1() {
    }

    public BinarySearchTree1(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size <= 0;
    }

    public void add(E element) {
        elementNotNullCheck(element);

        //如果是第一个节点
        if (size == 0) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        /**
         * 思路  找到父节点  创建一个新的节点， 然后根据大小决定该节点放在节点左边还是右边
         */

        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        while (node != null) {

            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = element;//覆盖
                return;
            }
        }

        Node<E> nodeNew = new Node<>(element, parent);

        if (cmp > 0) {
            parent.right = nodeNew;
        } else if (cmp < 0) {
            parent.left = nodeNew;
        }
        size++;
    }

    private int compare(E e1, E e2) {
        if (comparator != null) {//如果自定义的比较器为空
            return comparator.compare(e1, e2);
        }
        //使用对象的比较器  如果传入的对象没有实现Comparable接口，则报异常  因为平衡二叉树要求必须具备可比较性
        return ((Comparable<E>) e1).compareTo(e2);
    }

    //前序遍历
    public void preorderTraversal() {
        preorderTraversal(root);
    }

    public void preorderTraversal(Node<E> node) {
        if (node == null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);

    }

    //中序遍历
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    public void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);

    }


    //后序遍历
    public void lastOrderTraversal() {
        lastOrderTraversal(root);
    }

    public void lastOrderTraversal(Node<E> node) {
        if (node == null) return;
        lastOrderTraversal(node.left);
        lastOrderTraversal(node.right);
        System.out.println(node.element);

    }

    //层序遍历
    public void levelOrderTraversal() {
        levelOrderTraversal(root);
    }

    public void levelOrderTraversal(Node<E> node) {
        Queue<Node<E>> queue = new ArrayBlockingQueue(1000);
        queue.offer(node);
        while (queue.size() > 0) {
            Node<E> nodeTem = queue.poll();
            System.out.println(nodeTem.element);
            if (nodeTem.left != null) {
                queue.offer(nodeTem.left);
            }
            if (nodeTem.right != null) {
                queue.offer(nodeTem.right);
            }
        }

    }


    public void clear() {

    }

    public void remove() {

    }

    public boolean contains(E element) {
        return false;
    }

    public void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }


    /**
     * BinaryTreeInfo  : 属于二叉树打印工具的实现方法  有4个实现方法
     *
     * @return
     */
    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    //告知你要打印的元素
    @Override
    public Object string(Object node) {
        return ((Node<E>) node).element;
    }


    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }


}
